package others;


class ListNoded {
        public int value;
        public ListNoded next;
        public ListNoded() {
                value = 0;
                next = null;
        }
        
        public ListNoded(int value, ListNoded next) {
                this.value = value;
                this.next = next;
        }
}

public class MergeListProblem {
        public static ListNoded mergeLists(ListNoded head1, ListNoded head2) {
            
            // your code goes here
            //check the input
            if(head1 == null) return head2;
            if(head2 == null) return head1;
            
            
            
            ListNoded newHead = head1.value < head2.value ? head1 : head2;
            ListNoded indNew = newHead;
            
            ListNoded ind1 = head1.next, ind2 = head2.next;
            
            while(ind1 != null || ind2 != null){
                if(ind1 == null){
                    indNew.next = ind2;
                    ind2 = ind2.next;
                    continue;
                }
                
                if(ind2 == null){
                    indNew.next = ind1;
                    ind1 = ind1.next;
                    continue;
                }
                
                if(ind1.value < ind2.value){
                    indNew.next = ind1;
                    ind1 = ind1.next;
                    indNew = indNew.next;
                }else{
                    indNew.next = ind2;
                    ind2 = ind2.next;
                    indNew = indNew.next;
                }

            }
            
            //indNew.next = null;//tail
            
            return newHead;
        }
        
        public static void main(String[] args) {
        	ListNoded ind1 = new ListNoded(); ind1.value = 1;
        	ind1.next = new ListNoded(); ind1.next.value = 3;
        	ind1.next.next = new ListNoded(); ind1.next.next.value = 5;
        	

        	ListNoded ind2 = new ListNoded(); ind2.value = 2;
        	ind2.next = new ListNoded(); ind2.next.value = 4;
        	ind2.next.next = new ListNoded(); ind2.next.next.value = 4;
        	
        	ListNoded newHead = mergeLists(ind1, ind2);
        	System.out.println();
        }
}